﻿#define _CRT_SECURE_NO_WARNINGS 1
//Day18-01 牛客：压缩字符串（⼀），题号：2049875
//解法:字符串+模拟
//string compressString(string s)
//{
//    int n = s.size();
//    string ret;
//    int i = 0;
//    while (i < n) //双指针：i指针从前向后遍历，j指针去找相同字符
//    {
//        int j = i;
//        while (j + 1 < n && s[j + 1] == s[j]) j++;
//        ret += s[i];
//        int len = j - i + 1;
//        if (len != 1)
//            ret += to_string(len);
//        i = j + 1;
//    }
//    return ret;
//}


//Day18-02 牛客：chika和蜜柑，题号：374977
//解法:排序 / topK
//typedef long long LL;
//const int N = 2e5 + 10;
//int n, k;
//LL sour[N];
//LL sweet[N];
//
//struct cmp
//{
//    bool operator()(pair<LL, LL>p1, pair<LL, LL>p2)
//    {
//        if (p1.second == p2.second) return p1.first > p2.first;
//        return p1.second < p2.second;
//    }
//};
//
//int main()
//{
//    cin >> n >> k;
//    for (int i = 0; i < n; i++) cin >> sour[i];
//    for (int i = 0; i < n; i++) cin >> sweet[i];
//    priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, cmp> pq;
//    for (int i = 0; i < n; i++)
//    {
//        pq.push({ sour[i],sweet[i] });
//    }
//    LL sum_sour = 0, sum_sweet = 0;
//    while (k--)
//    {
//        auto [a, b] = pq.top(); pq.pop();
//        sum_sour += a;
//        sum_sweet += b;
//    }
//    cout << sum_sour << " " << sum_sweet << endl;
//    return 0;
//}


//Day18-03 牛客：01 背包，题号：1266316
//解法:动态规划 - 01背包
//int knapsack(int V, int n, vector<vector<int> >& vw)
//{
//    //dp[i][j]表示：从前i个物品中挑选，总体积不超过j,所能装的物品的最大重量
//    vector<vector<int>> dp(n + 1, vector<int>(V + 1));
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= V; j++)
//        {
//            //第i个物品不选
//            dp[i][j] = dp[i - 1][j];
//
//            //第i个物品选,体积v，重量w
//            int v = vw[i - 1][0], w = vw[i - 1][1];
//            if (j - v >= 0)
//                dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w);
//        }
//    }
//    return dp[n][V];
//}